An essential semiconductor device is semiconductor memory, such as a random access memory (RAM) device. A RAM allows a memory circuit to execute both read and write operations on its memory cells. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A conventional CAM is viewed as a static storage device constructed of modified RAM cells. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers, gateways and switches, computer systems and other devices that require rapid content searching, such as routing tables for data networks or matching URLs. Some of these tables are “learned” from the data passing through the network. Other tables, however, are fixed tables that are loaded into the CAM by a system controller. These fixed tables reside in the CAM for a relatively long period of time. A word in a CAM is typically very large and can be 96 bits or more.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location has one or a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every bit in memory with data in the comparand register. When the contents stored in the CAM memory location does not match the data in the comparand register, the local match detection circuit returns a no match indication. When the contents stored in the CAM memory location matches the data in the comparand register, the local match detection circuit returns a match indication. If one or more local match detect circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. In addition, the CAM may return the identification of the address location in which the desired data is stored or one of such addresses, if more than one address contained matching data. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memory.
Conventional CAMs use priority encoders to translate the physical location of a searched pattern that is located to a number/address identifying that pattern. Typically, priority encoders are designed as a major block common to the whole device. Such a design requires conductors from virtually every word in the CAM to be connected to the priority encoder. Typically, a priority encoder consists of two logical blocks—a highest priority indicator and an address encoder.
A priority encoder is a device with a plurality of inputs, wherein each of the inputs has an assigned priority. When an input is received on a high priority line in a highest priority indicator, all of the inputs of a lesser priority are disabled, forcing their associated outputs to remain inactive. If any numbers of inputs are simultaneously active, the highest priority indicator will activate only the output associated with the highest priority active input, leaving all other outputs inactive. Even if several inputs are simultaneously active, the priority encoder will indicate only the activity of the input with the highest priority. The priority address encoder is used in the CAM as the means to translate the position (within the CAM) of a matching word into a numerical address representing that location. The priority address encoder is also used to translate the location of only one word and ignore all other simultaneously matching words. However, often times, there is a need to resolve the priority among multiple inputs, each having a different assigned priority.
Furthermore, there is a need to effectively resolve “imperfect” matches, that is, stored CAM words that may match only a certain number of bits of the data in the comparand, but does not match every bit. Such CAM words are referred to as having a “longest match” condition. In prior art CAMs, search results typically require an exact match (i.e., 100% of the bits) before a system can process those results. Under one method, if an exact match is not found between the stored word and the full comparand, then selected bits in the comparand are masked and the search operation is repeated in an attempt to find a shorter match. If one bit of the comparand is masked at a time, then finding the longest match will require many repeated and undesirable operations/searches. Furthermore, as more bits become masked, multiple matches are indicated for any search result. Without a way to resolve multiple matches, users are typically left to examine the matches manually to find specific properties making one match more desirable than another.
In an alternative method, data in the CAM is stored in an ordered fashion, wherein data of a certain kind or location is assigned a higher priority, while data of another kind or location is given a lower priority. The priority can be established through assigned priority codes provided by a user. Like the first method described above, the alternative method also requires an exact match. Without an exact match, multiple search attempts are required, wherein, on each attempt, selected bits are masked so that they will not be involved in the matching process. As a result, several matches may be indicated for any search.
The alternative method is most often found in network communications, where routing tables are used to determine how a message is routed. Messages communicated through the network typically carry data pointing to the desired final destination, as well as topological data that informs the network of how the message is to be routed. Most network systems are configured in a way that only the last router, in a chain of routers in a network, will have the complete routing information and paths. All of the other routers in the path have information on only neighboring routers in a path. Accordingly, when a search is conducted on any router (other than the last router), the routing tables will not have the complete routing information, and will form matches between the searched routing information and the masked data available in the routing table.
Similar to the first method, a disadvantage of the alternative method is that multiple matching attempts have to be made before a usable match can be found. Secondly, the process of masking bits typically produces multiple matches, where users are left to re-examine each of the matches manually to prioritize the search results. Finally, CAM searches in network communication do not always require an exact match in order for the search to be useful. Often times, an imperfect match result contains sufficient network and “nearest router” data to be used to route the message. However, conventional network systems have not been able to process this data effectively to make use of a “longest match” condition. Accordingly, a system and method is thus needed to determine a “longest match” in a group of CAM words and assign a priority value to each of the longest matches in a single operation.